import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class TestHeap {
    public int[] elem;
    public int useSize;
    public TestHeap(){
        this.elem = new int[10];
    }

//    初始化数组
    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            useSize++;
        }
    }

//    创建大根堆
    public void createBingHeap(){
        for (int parent = (useSize-1-1)/2 ; parent >= 0 ; parent--) {
            siftDown1(parent,useSize);
        }
    }
//    向下调整大根堆  时间复杂度：log（N）
    private void siftDown1(int parent, int end){
        int child = parent*2 + 1;
        while(child < end){
            if (child + 1 < end && elem[child] < elem[child+1]){
                child++;
            }
            if ( elem[child] > elem[parent]){
                swap(child,parent);
                parent = child;
                child = parent*2 + 1;
            }else {
                break;
            }
        }
    }

//    向下调整小根堆
    private void siftDown2(int parent, int end){
        int child = parent*2 + 1;
        while(child < end){
            if (child + 1 < end && elem[child] > elem[child+1]){
                child++;
            }
            if ( elem[child] < elem[parent]){
                swap(child,parent);
                parent = child;
                child = parent*2 + 1;
            }else {
                break;
            }
        }
    }

    private void swap(int i,int j){
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp;
    }

//    有优先级队列的删除
    public int poll(){
        int temp = elem[0];
        swap(0,useSize-1);
        useSize--;
        siftDown1(0,useSize);
        return temp;
    }

//    优先级队列的插入
//    空间是否充足，不足够则扩容
    public void offer(int val){
//       1.判断栈满不满
        if (isFull()){
//            扩容
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
//        插入元素
        elem[useSize] = val;
        useSize++;
//        向上调整
        siftUp(useSize-1);
    }

//    向上调整  时间复杂度：log（N*logN)
    private void siftUp(int child){
        int parent = (child-1)/2;
        while(child > 0){
//            if ((child+1) > useSize  && elem[child] < elem[child+1]){
//               child++;
//            }

            if (elem[child] > elem[parent]){
                swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull(){
//        也可以直接 return useSize == elem.length
        if (useSize == elem.length){
            return true;
        }
        return false;
    }

//    输出前K个最小数据
    public int[] smallKey1(int[] arr, int k){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue();
//        时间复杂度：O(logN)
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[] tmp = new int[k];
//        时间复杂度：O(klogN)
        for (int i = 0; i < k; i++) {
            tmp[i] = priorityQueue.poll();
        }
        return tmp;
    }
//    第k个最小的数据
//    堆顶
//    输出前K个最小数据    关于堆的TOP-K问题
//    现将前k个数形成大根堆，之后比较的数字，若果比顶端小，则顶端元素去除，放入小元素，一直进行到结束
//    大根堆比较器
    class Imp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
    public int[] smallKey2(int[] arr,int k){
        int[] tmp = new int[k];
        if (k == 0){
            return tmp;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Imp());
//        将前k个元素放入大根堆
//        O(k)
        for (int i = 0; i < k; i++) {
            maxHeap.offer(arr[i]);
        }
//        O ((N-K)*logk)
        for (int i = k; i < arr.length; i++) {
            int top = maxHeap.peek();
            if (arr[i] < top){
//                这个时候堆顶的元素大，就要将大元素出出去
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }

//    堆排序  时间复杂度O(NlogN)：建堆O(N) 向上调整O(N*logN)
    public void headSort(){
//        前提是大根堆建立
//        先记录下最后一个下标
        int end = useSize-1;
        while(end>0){
//            将第一个元素与最后一个元素交换
            swap(0,end);
//            调整0小标这棵树，结束位置要小心
            siftDown1(0,end-1);
            end--;
        }
    }
}
